﻿//733.图像渲染
//有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
//你也被给予三个整数 sr, sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
//为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，
//接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，
//重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
//最后返回 经过上色渲染后的图像.

class Solution {
public:
    void dfs(vector<vector<int>>& image, int x, int y, int color)
    {
        int n = image.size();
        int m = image[0].size();
        int col = image[x][y];

        stack<pair<int, int>> sta;
        image[x][y] = color;
        sta.push({ x,y });
        while (!sta.empty())
        {
            pair<int, int> addr = sta.top();
            int r = addr.first;
            int c = addr.second;
            sta.pop();
            if (r - 1 >= 0 && image[r - 1][c] == col)
            {
                sta.push({ r - 1,c });
                image[r - 1][c] = color;
            }
            if (r + 1 < n && image[r + 1][c] == col)
            {
                sta.push({ r + 1,c });
                image[r + 1][c] = color;
            }
            if (c - 1 >= 0 && image[r][c - 1] == col)
            {
                sta.push({ r,c - 1 });
                image[r][c - 1] = color;
            }
            if (c + 1 < m && image[r][c + 1] == col)
            {
                sta.push({ r,c + 1 });
                image[r][c + 1] = color;
            }
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        if (color == image[sr][sc])
        {
            return image;
        }
        dfs(image, sr, sc, color);
        return image;
    }
};